home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 161_01 / qsortrcm.c < prev    next >
Encoding:
C/C++ Source or Header  |  1985-08-28  |  3.1 KB  |  114 lines
  1. /* qsort - sort array a (dimension n) using quicksort
  2.  * based on Bentley, CACM April 84
  3.  * Comments use notation A[i], a (fictitious) array of things
  4.  * that are of size elt_size.
  5.  */
  6. #include "local.h"
  7. /* swapfn - swap  elt_size bytes  a <--> b (internal routine) 
  8.  */
  9. static void swapfn(a, b, elt_size)
  10.     register char *a;    /* pointer to one element of A */
  11.     register char *b;    /* pointer to another element of A */
  12.     size_t elt_size;    /* size of each element */
  13.     {
  14.     register size_t i;
  15.     char tmp;
  16.  
  17.     LOOPDN(i, elt_size)
  18.         {
  19.         SWAP(*a, *b, tmp);
  20.         ++a, ++b;
  21.         }
  22.     }                                                                        /*
  23. .PE
  24. .PS 25
  25. /* iqsort - internal quicksort routine */
  26. static void iqsort(p_lo, p_hi, elt_size, cmpfn)
  27.     char *p_lo;            /* ptr to low element of (sub)array */
  28.     char *p_hi;            /* ptr to high element of (sub)array */
  29.     size_t elt_size;    /* size of each element */
  30.     int (*cmpfn)();        /* comparison function ptr */
  31.     {
  32.     char *p_mid;                /* pointer to middle element */
  33.     register char *p_i;            /* pointer to A[i] */
  34.     register char *p_lastlo;    /* pointer to A[lastlo] */
  35.  
  36.     if (p_hi <= p_lo)            /* is partition trivial? */
  37.         return;
  38.     p_mid = p_lo + ((((p_hi - p_lo) / elt_size) / 2) * elt_size);
  39.     swapfn(p_lo, p_mid, elt_size);    /* pick the middle element as pivot */
  40.     p_lastlo = p_lo;
  41.     for (p_i = p_lo + elt_size;  p_i <= p_hi; p_i += elt_size)
  42.         {
  43.         if ((*cmpfn)(p_lo, p_i) > 0)
  44.             {
  45.             p_lastlo += elt_size;
  46.             swapfn(p_lastlo, p_i, elt_size);
  47.             }
  48.         }
  49.     swapfn(p_lo, p_lastlo, elt_size);
  50.     iqsort(p_lo, p_lastlo - elt_size, elt_size, cmpfn);
  51.     iqsort(p_lastlo + elt_size, p_hi, elt_size, cmpfn);
  52.     }                                                                        /*
  53. .PE
  54. .PS 9
  55. /* qsort - the callable entry point */
  56. void qsort(a, n, size, pf)
  57.     data_ptr a;        /* address of array A to be sorted */
  58.     size_t n;        /* number of elements in A */
  59.     size_t size;    /* size of each element */
  60.     int (*pf)();    /* comparison function ptr */
  61.     {
  62.     iqsort((char *)a, (char *)a + (n-1) * size, size, pf);
  63.     }
  64. /* qsortm - test the qsort function
  65.  */
  66. #include "local.h"
  67. #include "cputim.h"
  68. static long n_compares = 0;
  69. static int a[10000] = {0};
  70. /* intcmp - compare two ints */
  71. int intcmp(pi, pj)
  72.     register int *pi, *pj;
  73.     {
  74.     ++n_compares;
  75.     if (*pi < *pj)
  76.         return (-1);
  77.     else if (*pi == *pj)
  78.         return (0);
  79.     else
  80.         return (1);
  81.     }
  82. /* qsortm (main) - run the test */
  83. main(ac, av)
  84.     int ac;
  85.     char *av[];
  86.     {
  87.     int i;
  88.     int lim;
  89.     double nlogn;
  90.     double tim;    /* in usec */
  91.     cputim_t cputim();
  92.  
  93.     lim = atoi(av[1]);
  94.     printf("lim=%d\n", lim);
  95.     for (i = 0; i < lim; ++i)
  96.         a[i] = rand();
  97.     printf("start:\n");
  98.     cputim();
  99.     qsort((data_ptr)a, lim, sizeof(int), intcmp);
  100.     tim = 1e6 * (double)cputim() / CLOCK_TICKS_PER_SECOND;
  101.     printf("cpu time = %.3f (sec)\n", tim / 1e6);
  102.     nlogn = lim * log((double)lim) / log(2.);
  103.     printf("n_compares = %ld\n", n_compares);
  104.     printf("cpu time = %.3f (usec) per compare\n", tim / n_compares);
  105.     printf("log N = %.3f\n", log((double)lim) / log(2.));
  106.     printf("N log N = %.3f\n", nlogn);
  107.     printf("cpu time = %.2f N log N (usec)\n", tim / nlogn);
  108.     printf("ratio of n_compares to N log N = %.3f\n\n", n_compares / nlogn);
  109.     for (i = 0; i < lim-1; ++i)
  110.         if (a[i] > a[i+1])
  111.             error("bad value", "");
  112.     exit(SUCCEED);
  113.     }
  114.